\documentclass[10pt, french]{beamer}

\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[frenchb]{babel}
\usepackage{graphicx}
\usepackage{amsmath}

\selectlanguage{french}

\usetheme{Frankfurt}

\AtBeginSection[]
{
   \begin{frame}
       \frametitle{Plan}
       \tableofcontents[currentsection]
   \end{frame}
}

\title[MEMO-F-500 - Mémoire de fin d'études]{Distribution de code dSL avec contraintes}
\subtitle{MEMO-F-500 - Mémoire de fin d'études}
\author{Olivier Sputael}
\institute[U.L.B.]{Universit\'e Libre de Bruxelles (U.L.B.), Belgique}
\date{\today}

\begin{document}

\frame{\titlepage}

\begin{frame}{Plan}
	\tableofcontents
\end{frame}

\section{Contexte}
\begin{frame}{dSL}
	\textit{Distributed} Supervision Language
	\medskip
	\begin{center}
		\includegraphics[scale=0.8]{images/distrib.pdf}
	\end{center}
\end{frame}

\begin{frame}[fragile]{Types de blocs en dSL}
	\begin{tabular}{l | l}
		Bloc atomique & Bloc séquentiel \\
		& \\
		\texttt{WHEN} \textsl{condition} \texttt{THEN} & \texttt{SEQUENCE} \textsl{maSequence (params)} \\
		\texttt{\; \; a := 1;} & \texttt{\; \; a := 1} \\
		\texttt{\; \; b := 2;} & \texttt{\; \; b := 2} \\
		\texttt{\; \; c := FALSE} & \texttt{\; \; c := FALSE} \\
		\texttt{END\_WHEN} & \texttt{END\_SEQUENCE} \\
	\end{tabular}
\end{frame}

\begin{frame}[fragile]{Types de blocs en dSL}
	\begin{tabular}{l | l}
		Bloc atomique & Bloc séquentiel \\
		& \\
		%\begin{center}
			\includegraphics[scale=0.3]{images/atomic.pdf}
		%\end{center}
		 & 
		%\begin{center}
			\includegraphics[scale=0.3]{images/sequential.pdf}
		%\end{center}
	\end{tabular}
\end{frame}

\begin{frame}[fragile]{Distribution}
	\begin{itemize}
		\item Étape 1: distribution des instructions atomiques
			\begin{itemize}
				\item contraintes sur certaines variables
			\end{itemize}
		\medskip
		\item Étape 2: finition de la distribution
			\begin{itemize}
				\item minimisation des transmissions
			\end{itemize}
	\end{itemize}
	\medskip
	\begin{center}
		\includegraphics[scale=0.3]{images/transmission.pdf}
	\end{center}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Motivation de la recherche}
\begin{frame}{La redistribution}
	\begin{itemize}
		\item Modification d'une application $\Rightarrow$ redistribution
		\medskip
		\item Actuellement: distribution d'une \textit{nouvelle} application
		\medskip
		\item Volonté du programmeur: garder la structure
	\end{itemize}
\end{frame}

%\begin{frame}{Etapes de la distribution}
%	\begin{enumerate}
%		\item Contraintes sur certaines variables globales
%		\bigskip
%		\item Distribution des instructions liées à ces contraintes
%		\bigskip
%		\item Distribution des instructions restantes
%	\end{enumerate}
%\end{frame}
%\begin{frame}{Distribution des instructions liées aux contraintes}
%	\begin{itemize}
%		\item Liaison directe
%		\medskip
%		\item Liaison indirecte
%	\end{itemize}
%	\begin{center}
%		\includegraphics[scale=1.5]{images/graph.jpg}
%	\end{center}
%\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Méthode de redistribution: la théorie}
\begin{frame}{Les critères à respecter}
	\begin{itemize}
		\item Deux critères: 
			\medskip
			\begin{enumerate}
				\item Conservation de la structure ($C_r$)
				\medskip
				\item Minimisation de la transmission ($C_t$)
			\end{enumerate}
			\medskip
		\item Création d'un coût général: 
			\medskip
			\begin{equation}
				O_d = \alpha C_r + \beta C_t
			\end{equation}
	\end{itemize}
\end{frame}

\begin{frame}{Démarche: \textit{divide and conquer}}
	Décomposition du problème en sous-problèmes: 
	\bigskip
	\begin{enumerate}
		\item Comparaison des deux versions du code
		\medskip
		\item Redistribution
			\medskip
			\begin{itemize}
				\item en respectant les contraintes
				\medskip
				\item en minimisation le coût général
			\end{itemize}
	\end{enumerate}
\end{frame}

\begin{frame}{La comparaison}
	\begin{itemize}
		\item Problèmes similaires:
			\medskip
			\begin{itemize}
				\item Isomorphisme de (sous-)graphes
				\medskip
				\item \textbf{Sous-graphe commun maximum}
				\medskip
				\item ...
			\end{itemize}
		\medskip
		\item Difficulté: problème NP-complet !
		\medskip
		\item Solution: simplification des graphes
	\end{itemize}
\end{frame}

\begin{frame}{Algorithme de comparaison}
	\begin{itemize}
		\item But: trouver les paires de n\oe{}uds identiques
		\medskip
		\item Étape 1: ensemble de paires candidates
		\medskip
		\item Étape 2: trouver une paire de n\oe{}uds identiques
	\end{itemize}
\end{frame}

\begin{frame}{La redistribution}
	\begin{itemize}
		\item La \textit{pré-redistribution}
			\medskip
			\begin{itemize}
				\item en tenant compte des contraintes
			\end{itemize}
			\medskip
		\item La redistribution des n\oe{}uds identiques
			\medskip
			\begin{itemize}
				\item en tenant compte des résultats de la comparaison
			\end{itemize}
			\medskip
		\item La finition de la redistribution
			\medskip
			\begin{itemize}
				\item minimisation du coût général
			\end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{La finition de la redistribution}
	\begin{equation*}
		Min \left( \alpha C_r + \beta C_t \right)
	\end{equation*}
	\begin{itemize}
		\item Problème d'optimisation (ici: minimisation)
		\medskip
		\item Solution par \textit{Branch \& Bound}
	\end{itemize}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{La pratique}
\begin{frame}{L'implémentation}
	Démonstration
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\section{Conclusion}
%\begin{frame}{Conclusion}
%	
%\end{frame}

\begin{frame}{Questions ?}
	Merci pour votre attention !
	\medskip
	\begin{center}
		\includegraphics[scale=0.5]{images/question.jpg}
	\end{center}
\end{frame}

\end{document}